package Test;

public class test03 {
        public static String minWindow(String s, String t) {
            char[] ch1 = s.toCharArray();
            char[] ch2 = t.toCharArray();
            int n = s.length();
            int m = t.length();
            int[] hash1 = new int[128];
            int count1 = 0;//统计t字符串中单词的种类
            //Hash1: 统计t字符串中字符出现的的次数
            for(int i=0;i<m;i++){
                if(hash1[ch2[i]]==0) count1++;//统计种类
                hash1[ch2[i]]++;//ch2[i]单词的次数+1
            }
            int r = 0;
            int l = 0;
            int[] hash2 = new int[128];
            int count2 = 0;//统计s中的单词和 t中的单词的个数相同时的个数
            int minlen = n+1;
            int begl = -1;
            while(r<n){
                //进窗口:
                hash2[ch1[r]]++;
                //判断:
                if(hash2[ch1[r]]==hash1[ch1[r]]) count2++;
                //统计结果:
                while(count1==count2){
                    if(minlen>r-l+1){
                        minlen = r-l+1;
                        begl = l;
                    }
                    if(hash2[ch1[l]]==hash1[ch1[l]]) count2--;
                    //出窗口:
                    hash2[ch1[l]]--;
                    l++;
                }
                r++;
            }
            return begl==-1?"":s.substring(begl,begl+minlen);
        }

    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        String s1 = minWindow(s, t);
        System.out.println(s1);
    }
}
